﻿public class MyDictionary<TKey,TValue>
{
    private struct Entry{
        public int hashCode;//哈希值
        public int next;//下一个条目
        public TKey key;//key
        public TValue value;//value
    }

    private int[] buckets;//桶数组
    private Entry[] entries;//条目数组
    private int count;//当前条目数量

    private int capacity;//大小


    public MyDictionary(int capacity = 16){
        this.buckets = new int[capacity];
        this.entries = new Entry[capacity];
        this.capacity = capacity;
        this.count = 0;
        for(int i=0;i<this.buckets.Length;i++){
            this.buckets[i]=-1;
        }
    }


    public void Add(TKey key,TValue value){

        if(this.count>=this.capacity){
            Console.WriteLine("容量已达到上限");
            return ;
        }
        //拉链法添加数据
        int hashCode = key.GetHashCode();
        int targetBucket = hashCode % this.buckets.Length;
        for(int i=this.buckets[targetBucket];i>=0;i=this.entries[i].next){
            if(this.entries[i].hashCode==hashCode&&this.entries[i].key.Equals(key)){
                if(this.entries[i].value.Equals(value)){
                    Console.WriteLine("该值已经存在。");
                    
                }else{
                    this.entries[i].value = value;
                }
                return; 
            }
        }

        Entry newEntry = new Entry{
          hashCode = hashCode,
          key = key,
          value = value,
          next = this.buckets[targetBucket]  
        };

        //将位置信息插入头部
        this.buckets[targetBucket] = this.count;
        //数据归置
        this.entries[this.count] = newEntry;
        //个数增加
        this.count ++; 
    }

    public TValue Get(TKey key){
        int hashCode = key.GetHashCode();
        int targetBucket = hashCode % this.buckets.Length;
        for(int i=this.buckets[targetBucket];i>=0;i=this.entries[i].next){
            if(this.entries[i].hashCode==hashCode&&this.entries[i].key.Equals(key))
            {
                return this.entries[i].value;
            }
        }

        throw new KeyNotFoundException();
    }
}

public class Program{
    public static void Main(){
        Console.WriteLine("===============================================");
        MyDictionary<int,int> myDictionary = new MyDictionary<int, int>(10);

        myDictionary.Add(1,1001);
        int v = myDictionary.Get(1);
        Console.WriteLine(v);

        for(int i=0;i<11;i++){
            Console.WriteLine(i);
            myDictionary.Add(i,100+i);
        }

        for(int i=0;i<10;i++){
            v = myDictionary.Get(i);
            Console.WriteLine(v);
        }
    }
}

